Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Note that an empty string is also considered valid.
Example 1:
1 2
Input: "()" Output: true
Example 2:
1 2
Input: "()[]{}" Output: true
Example 3:
1 2
Input: "(]" Output: false
Example 4:
1 2
Input: "([)]" Output: false
Example 5:
1 2
Input: "{[]}" Output: true
方法1：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
class Solution { public boolean isValid(String s) { Map<Character,Character> m = new HashMap<Character,Character>(); m.put(')', '('); m.put('}', '{'); m.put(']', '[');
Stack<Character> stack = new Stack<Character>(); for (char key : s.toCharArray()) { if (!m.containsKey(key)) { stack.push(key); } else if (stack.empty() || !m.get(key).equals(stack.pop())) { return false; } } return stack.empty();